package DynamicProgramming;//给定一个非空字符串 s 和一个包含非空单词列表的字典 wordDict，在字符串中增加空格来构建一个句子，使得句子中所有的单词都在词典中。返回所有这些可能的
//句子。 
//
// 说明： 
//
// 
// 分隔时可以重复使用字典中的单词。 
// 你可以假设字典中没有重复的单词。 
// 
//
// 示例 1： 
//
// 输入:
//s = "catsanddog"
//wordDict = ["cat", "cats", "and", "sand", "dog"]
//输出:
//[
//  "cats and dog",
//  "cat sand dog"
//]
// 
//
// 示例 2： 
//
// 输入:
//s = "pineapplepenapple"
//wordDict = ["apple", "pen", "applepen", "pine", "pineapple"]
//输出:
//[
//  "pine apple pen apple",
//  "pineapple pen apple",
//  "pine applepen apple"
//]
//解释: 注意你可以重复使用字典中的单词。
// 
//
// 示例 3： 
//
// 输入:
//s = "catsandog"
//wordDict = ["cats", "dog", "sand", "and", "cat"]
//输出:
//[]
// 
// Related Topics 字典树 记忆化搜索 哈希表 字符串 动态规划 回溯 👍 533 👎 0


import java.util.ArrayList;
import java.util.List;

//leetcode submit region begin(Prohibit modification and deletion)
class wordBreakII {

    List<String> res = new ArrayList<>(); //结果集
    List<String> path = new ArrayList<>(); //中间集
    public List<String> wordBreak(String s, List<String> wordDict) {
        //首先对样例进行一个检测，不能被拆分的直接返回
        if(s==null || s.length()==0){
            return res;
        }
        int len = s.length();
        //不能被拆分
        if(!isValid(s,wordDict,len)){
            return res;
        }
        //能被拆分的用 回溯解决
        dfs(s,0,len,wordDict);
        return res;


    }

    private void dfs(String s, int start, int len, List<String> wordDict){
        //到叶子节点 可以收集结果 
        if(start>=len){
            StringBuilder sb = new StringBuilder();
            for(int i=0;i<path.size();i++){
                if(i<path.size()-1){
                    sb.append(path.get(i)+" ");
                }else{
                    sb.append(path.get(i));
                }

            }
            res.add(sb.toString());
            return;
        }
        for(int i=1;i<=len;i++){
            //该层后面的不需要进行，因为越届了
            if(i+start > len){
                break;
            }
            //如果当前截取的字符串在集合中，将该字符串加入中间集
            String str  = s.substring(start,i+start);
            if(wordDict.contains(str)){
                path.add(str);
                dfs(s,i+start,len,wordDict);
                path.remove(path.size()-1);
            }

        }
    }

    //判断是否能被拆分
    private  boolean isValid(String s, List<String> wordDict, int len){
        //动态规划 dp[i]表示[0,i]的范围字符串是否在wordDict中
        boolean[] dp = new boolean[len+1];
        //初始化
        dp[0] = true;
        for(int i=1;i<=len;i++){
            for(int j=0;j<i;j++){
                //dp[i]取决于 上一段dp[j]是否为true和 [j,i+j]这一范围是否在集合中
                if(wordDict.contains(s.substring(j,i)) && dp[j]){
                    dp[i] = true;
                }
            }
        }
        return dp[len];
    }
}
//leetcode submit region end(Prohibit modification and deletion)
